#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2022/5/11 21:45
# @Author  : Yizheng Dai
# @Email   : 387942239@qq.com
# @File    : _47_.py
from copy import deepcopy


class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        use = [False] * len(nums)

        path = []
        res = []

        def dfs():
            if len(path) == len(nums):
                res.append(deepcopy(path))
                return
            for idx in range(len(nums)):
                if use[idx]: continue
                path.append(nums[idx])
                use[idx] = True
                dfs()
                path.pop()
                use[idx] = False

        dfs()
        ans = []
        for it in res:
            if it not in ans:
                ans.append(it)

        return ans
    
    # 在循环中剪枝
    def permuteUnique1(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ## 排序
        nums = sorted(nums)
        use = [False] * len(nums)

        path = []
        res = []

        def dfs():
            if len(path) == len(nums):
                res.append(deepcopy(path))
                return
            for idx in range(len(nums)):
                if use[idx] : continue
                ## 剪枝
                # if idx>0 and nums[idx] == nums[idx-1] and not use[idx-1]:continue 
                path.append(nums[idx])
                use[idx] = True
                dfs()
                path.pop()
                use[idx] = False
        dfs()
        return res


if __name__ == '__main__':
    a = Solution().permuteUnique1([1,1,2])
    print(a)